home *** CD-ROM | disk | FTP | other *** search
/ Computer Select (Limited Edition) / Computer Select.iso / dobbs / v16n09 / bob12.exe / BOBMEM.C < prev    next >
Encoding:
C/C++ Source or Header  |  1991-08-28  |  13.7 KB  |  568 lines
  1. /* bobmem.c - memory manager */
  2. /*
  3.     Copyright (c) 1991, by David Michael Betz
  4.     All rights reserved
  5. */
  6.  
  7. #include <setjmp.h>
  8. #include "bob.h"
  9.  
  10. /* allocation unit */
  11. typedef char *AUNIT;
  12. #define ALLOCSIZE(x)    (((x) + sizeof(AUNIT) - 1) / sizeof(AUNIT))
  13.  
  14. /* block flags */
  15. #define MARK    1
  16.  
  17. /* size of each type of memory segment */
  18. #define VSSIZE    10000    /* number of LVAL's per vector segment */
  19. #define VCOMPARE(f,s,t)    ((f) + (s) <= (t))
  20.  
  21. /* macros to compute the size of a segment */
  22. #define vsegsize(n) (sizeof(VSEGMENT)+((n)-1)*sizeof(char *))
  23.  
  24. /* macro to convert a byte size to a word size */
  25. #define btow_size(n)    (((n) + sizeof(char *) - 1) / sizeof(char *))
  26.  
  27. /* vector segment structure */
  28. typedef struct vsegment {
  29.     struct vsegment *vs_next;    /* next vector segment */
  30.     AUNIT *vs_free;        /* next free location in this segment */
  31.     AUNIT *vs_top;        /* top of segment (plus one) */
  32.     AUNIT vs_data[1];        /* segment data */
  33. } VSEGMENT;
  34.  
  35. /* global variables */
  36. VALUE symbols;    /* the symbol table */
  37. VALUE classes;    /* the class table */
  38. VALUE nil;    /* the nil value */
  39.  
  40. /* vector (and string) space */
  41. static VSEGMENT *vsegments=NULL;/* list of vector segments */
  42. static VSEGMENT *vscurrent=NULL;/* current vector segment */
  43. static AUNIT *vfree=NULL;    /* next free location in current segment */
  44. static AUNIT *vtop=NULL;    /* top of current segment */
  45.  
  46. /* external variables */
  47. extern jmp_buf error_trap;    /* the error trap target */
  48. extern VECTOR *code;        /* currently executing code vector */
  49.  
  50. /* forward declarations */
  51. void mark();
  52. static HDR *allocmemory();
  53. static void gc(),markclass(),markdictionary(),markentry(),markobject();
  54. static void markvector(),compact(),compact_vector();
  55. static DICT_ENTRY *newentry();
  56.  
  57. /* initialize - initialize the virtual machine */
  58. int initialize(smax,cmax)
  59.   int smax,cmax;
  60. {
  61.     int obj_class(),cls_new();
  62.     char *calloc();
  63.     
  64.     /* setup an error trap handler */
  65.     if (setjmp(error_trap) != 0)
  66.     return (FALSE);
  67.  
  68.     /* allocate the stack */
  69.     if ((stkbase = (VALUE *)calloc(1,smax * sizeof(VALUE))) == NULL)
  70.     return (FALSE);
  71.     stktop = sp = stkbase + smax;
  72.     code = NULL;
  73.  
  74.     /* initialize the memory manager */
  75.     vsegments = vscurrent = NULL;
  76.     vfree = vtop = NULL;
  77.     if (!vexpand(VSSIZE))
  78.     return (FALSE);
  79.  
  80.     /* initialize the compiler */
  81.     if (!init_compiler(cmax))
  82.     return (FALSE);
  83.  
  84.     /* create the symbol and class tables */
  85.     set_nil(&nil);
  86.     set_dictionary(&symbols,newdictionary(&nil));
  87.     set_dictionary(&classes,newdictionary(&nil));
  88.  
  89.     /* enter the built-in functions */
  90.     init_functions();
  91.     return (TRUE);
  92. }
  93.  
  94. /* addentry - add an entry to a dictionary */
  95. DICT_ENTRY *addentry(dict,key,type)
  96.   VALUE *dict; char *key; int type;
  97. {
  98.     DICT_ENTRY *entry;
  99.     if ((entry = findentry(dict,key)) == NULL) {
  100.     check(1);
  101.     push_var(newentry(dict,key,type));
  102.     sp->v.v_var->de_next = *digetcontents(dict);
  103.     dict->v.v_dictionary->di_contents = *sp;
  104.     entry = deaddr(sp++);
  105.     }
  106.     return (entry);
  107. }
  108.  
  109. /* findentry - find an entry in a dictionary */
  110. DICT_ENTRY *findentry(dict,key)
  111.   VALUE *dict; char *key;
  112. {
  113.     DICT_ENTRY *entry;
  114.     for (entry = digetcontents(dict)->v.v_var;
  115.      entry != NULL;
  116.      entry = entry->de_next.v.v_var)
  117.     if (strncmp(key,
  118.             strgetdata(&entry->de_key),
  119.             strgetsize(&entry->de_key)) == 0)
  120.         return (entry);
  121.     return (NULL);
  122. }
  123.  
  124. /* makestring - make an initialized string from a C-style string */
  125. STRING *makestring(str)
  126.   char *str;
  127. {
  128.     STRING *val;
  129.     int len;
  130.     len = strlen(str);
  131.     val = newstring(len);
  132.     strncpy(val->str_data,str,len);
  133.     return (val);
  134. }
  135.  
  136. /* getcstring - get a C-style version of a string */
  137. char *getcstring(buf,max,str)
  138.   char *buf; int max; VALUE *str;
  139. {
  140.     int len;
  141.     if ((len = strgetsize(str)) >= max)
  142.     len = max - 1;
  143.     strncpy(buf,strgetdata(str),len);
  144.     buf[len] = '\0';
  145.     return (buf);
  146. }
  147.  
  148. /* newstring - allocate a new string object */
  149. STRING *newstring(n)
  150.   int n;
  151. {
  152.     STRING *val;
  153.     int size;
  154.     char *p;
  155.     size = sizeof(STRING) + n - 1;
  156.     val = (STRING *)allocmemory(DT_STRING,size);
  157.     val->str_size = n;
  158.     for (p = val->str_data; --n >= 0; )
  159.     *p++ = '\0';
  160.     return (val);
  161. }
  162.  
  163. /* newobject - allocate a new object */
  164. OBJECT *newobject(class)
  165.   VALUE *class;
  166. {
  167.     OBJECT *val;
  168.     int size,n;
  169.     VALUE *p;
  170.     n = clgetsize(class);
  171.     size = sizeof(OBJECT) + (n - 1) * sizeof(VALUE);
  172.     val = (OBJECT *)allocmemory(DT_OBJECT,size);
  173.     val->obj_class = *class;
  174.     for (p = val->obj_members; --n >= 0; ++p)
  175.     p->v_type = DT_NIL;
  176.     return (val);
  177. }
  178.  
  179. /* newvector - allocate a new vector */
  180. VECTOR *newvector(n)
  181.   int n;
  182. {
  183.     VECTOR *val;
  184.     VALUE *p;
  185.     int size;
  186.     size = sizeof(VECTOR) + (n - 1) * sizeof(VALUE);
  187.     val = (VECTOR *)allocmemory(DT_VECTOR,size);
  188.     val->vec_size = n;
  189.     for (p = val->vec_data; --n >= 0; ++p)
  190.     p->v_type = DT_NIL;
  191.     return (val);
  192. }
  193.  
  194. /* newclass - create a new class */
  195. CLASS *newclass(name,base)
  196.   char *name; VALUE *base;
  197. {
  198.     /* allocate the memory for the new class */
  199.     check(1);
  200.     push_class((CLASS *)allocmemory(DT_CLASS,sizeof(CLASS)));
  201.     set_nil(&sp->v.v_class->cl_name);
  202.     set_nil(&sp->v.v_class->cl_members);
  203.     set_nil(&sp->v.v_class->cl_functions);
  204.  
  205.     /* initialize */
  206.     sp->v.v_class->cl_base = *base;
  207.     set_string(&sp->v.v_class->cl_name,makestring(name));
  208.     set_dictionary(&sp->v.v_class->cl_members,newdictionary(sp));
  209.     set_dictionary(&sp->v.v_class->cl_functions,newdictionary(sp));
  210.     sp->v.v_class->cl_size = 0;
  211.  
  212.     /* return the new class */
  213.     return (claddr(sp++));
  214. }
  215.  
  216. /* newdictionary - create a new dictionary */
  217. DICTIONARY *newdictionary(class)
  218.   VALUE *class;
  219. {
  220.     DICTIONARY *dict;
  221.     dict = (DICTIONARY *)allocmemory(DT_DICTIONARY,sizeof(DICTIONARY));
  222.     dict->di_class = *class;
  223.     set_nil(&dict->di_contents);
  224.     return (dict);
  225. }
  226.  
  227. /* newentry - allocate a new dictionary entry */
  228. static DICT_ENTRY *newentry(dict,key,type)
  229.   VALUE *dict; char *key; int type;
  230. {
  231.     check(1);
  232.     push_var((DICT_ENTRY *)allocmemory(DT_VAR,sizeof(DICT_ENTRY)));
  233.     sp->v.v_var->de_dictionary = *dict;
  234.     sp->v.v_var->de_type = type;
  235.     set_nil(&sp->v.v_var->de_key);
  236.     set_nil(&sp->v.v_var->de_value);
  237.     set_nil(&sp->v.v_var->de_next);
  238.     set_string(&sp->v.v_var->de_key,makestring(key));
  239.     return (deaddr(sp++));
  240. }
  241.  
  242. /* allocmemory - allocate a block of memory */
  243. static HDR *allocmemory(type,size)
  244.   int type,size;
  245. {
  246.     HDR *val;
  247.  
  248.     /* make sure there's enough space */
  249.     size = ALLOCSIZE(size);
  250.     if (!VCOMPARE(vfree,size,vtop)
  251.     &&  !checkvmemory(size)
  252.     &&  !findvmemory(size))
  253.     error("Insufficient memory");
  254.  
  255.     /* allocate the next available block */
  256.     val = (HDR *)vfree;
  257.     vfree += size;
  258.     
  259.     /* return the new block of memory */
  260.     val->hdr_type = type;
  261.     val->hdr_flags = 0;
  262.     val->hdr_chain = NULL;
  263. /*printf("ALLOC: %04x T:%02d S:%d\n",val,type,size);*/
  264.     return (val);
  265. }
  266.  
  267. /* findvmemory - find vector memory */
  268. static int findvmemory(size)
  269.   int size;
  270. {
  271.     /* try garbage collecting */
  272.     gc();
  273.  
  274.     /* check to see if we found enough memory */
  275.     if (VCOMPARE(vfree,size,vtop) || checkvmemory(size))
  276.     return (TRUE);
  277.  
  278.     /* expand vector space */
  279.     return (makevmemory(size));
  280. }
  281.  
  282. /* checkvmemory - check for vector memory (used by 'xsimage.c') */
  283. static int checkvmemory(size)
  284.   int size;
  285. {
  286.     VSEGMENT *vseg;
  287.     for (vseg = vsegments; vseg != NULL; vseg = vseg->vs_next)
  288.     if (vseg != vscurrent && VCOMPARE(vseg->vs_free,size,vseg->vs_top)) {
  289.         if (vscurrent != NULL)
  290.         vscurrent->vs_free = vfree;
  291.         vfree = vseg->vs_free;
  292.         vtop = vseg->vs_top;
  293.         vscurrent = vseg;
  294.         return (TRUE);
  295.     }    
  296.     return (FALSE);
  297. }
  298.     
  299. /* makevmemory - make vector memory (used by 'xsimage.c') */
  300. static int makevmemory(size)
  301.   int size;
  302. {
  303.     return (vexpand(size < VSSIZE ? VSSIZE : size));
  304. }
  305.  
  306. /* vexpand - expand vector space */
  307. static int vexpand(size)
  308.   int size;
  309. {
  310.     VSEGMENT *newvsegment(),*vseg;
  311.  
  312.     /* allocate the new segment */
  313.     if ((vseg = newvsegment(size)) != NULL) {
  314.  
  315.     /* initialize the new segment and make it current */
  316.     if (vscurrent != NULL)
  317.         vscurrent->vs_free = vfree;
  318.     vfree = vseg->vs_free;
  319.     vtop = vseg->vs_top;
  320.     vscurrent = vseg;
  321.     }
  322.     return (vseg != NULL);
  323. }
  324.  
  325. /* newvsegment - create a new vector segment */
  326. static VSEGMENT *newvsegment(n)
  327.   unsigned int n;
  328. {
  329.     char *calloc();
  330.     VSEGMENT *newseg;
  331.  
  332.     /* allocate the new segment */
  333.     if ((newseg = (VSEGMENT *)calloc(1,vsegsize(n))) == NULL)
  334.     return (NULL);
  335.  
  336.     /* initialize the new segment */
  337.     newseg->vs_free = newseg->vs_data;
  338.     newseg->vs_top = newseg->vs_free + n;
  339.     newseg->vs_next = vsegments;
  340.     vsegments = newseg;
  341.  
  342.     /* return the new segment */
  343.     return (newseg);
  344. }
  345.  
  346. /* gc - garbage collect */
  347. static void gc()
  348. {
  349.     extern unsigned char *cbase,*pc;
  350.     VALUE codeval,*p;
  351.     LITERAL *lit;
  352.     int pcoff;
  353.  
  354. /*printf("[GC]\n");*/
  355.     /* protect the current bytecode vector */
  356.     if (code) {
  357.     set_bytecode(&codeval,code);
  358.     pcoff = pc - cbase;
  359.     mark(&codeval);
  360.     }
  361.  
  362.     /* mark all reachable values */
  363.     mark(&symbols);
  364.     mark(&classes);
  365.  
  366.     /* mark the stack */
  367.     for (p = sp; p < stktop; )
  368.     mark(p++);
  369.  
  370.     /* mark compiler variables */
  371.     mark_compiler();
  372.  
  373.     /* compact all active blocks */
  374.     compact();
  375.  
  376.     /* reload the interpreter's registers */
  377.     if (code) {
  378.     code = codeval.v.v_vector;
  379.     cbase = code->vec_data[0].v.v_string->str_data;
  380.     pc = cbase + pcoff;
  381.     }
  382. }
  383.  
  384. /* mark - mark all accessible nodes */
  385. void mark(val)
  386.   VALUE *val;
  387. {
  388.     HDR *hdr;
  389. /*printf("MARKING: %04x T:%02d H:%04x\n",val,val->v_type,val->v.v_hdr);*/
  390.     switch (val->v_type) {
  391.     case DT_CLASS:
  392.     case DT_OBJECT:
  393.     case DT_VECTOR:
  394.     case DT_BYTECODE:
  395.     case DT_STRING:
  396.     case DT_DICTIONARY:
  397.     case DT_VAR:
  398.     hdr = val->v.v_hdr;
  399.     val->v.v_chain = hdr->hdr_chain;
  400.     hdr->hdr_chain = val;
  401.     if ((hdr->hdr_flags & MARK) == 0) {
  402.         hdr->hdr_flags |= MARK;
  403.         switch (hdr->hdr_type) {
  404.         case DT_CLASS:
  405.         markclass((CLASS *)hdr);
  406.         break;
  407.         case DT_OBJECT:
  408.         markobject((OBJECT *)hdr);
  409.         break;
  410.         case DT_VECTOR:
  411.         markvector((VECTOR *)hdr);
  412.         break;
  413.         case DT_DICTIONARY:
  414.         markdictionary((DICTIONARY *)hdr);
  415.         break;
  416.         case DT_VAR:
  417.         markentry((DICT_ENTRY *)hdr);
  418.         break;
  419.         }
  420.     }
  421.     break;
  422.     }
  423. }
  424.  
  425. /* markclass - mark a class */
  426. static void markclass(class)
  427.   CLASS *class;
  428. {
  429.     mark(&class->cl_name);
  430.     mark(&class->cl_base);
  431.     mark(&class->cl_members);
  432.     mark(&class->cl_functions);
  433. }
  434.  
  435. /* markdictionary - mark a dictionary */
  436. static void markdictionary(dict)
  437.   DICTIONARY *dict;
  438. {
  439.     VALUE *next,*val;
  440.     mark(&dict->di_class);
  441.     for (val = &dict->di_contents;
  442.      !isnil(val);
  443.      val = next) {
  444.     next = degetnext(val);
  445.     mark(val);
  446.     }
  447. }
  448.  
  449. /* markentry - mark a dictionary entry */
  450. static void markentry(entry)
  451.   DICT_ENTRY *entry;
  452. {
  453.     mark(&entry->de_dictionary);
  454.     mark(&entry->de_key);
  455.     mark(&entry->de_value);
  456. }
  457.  
  458. /* markobject - mark an object */
  459. static void markobject(obj)
  460.   OBJECT *obj;
  461. {
  462.     VALUE *p;
  463.     int n;
  464.     p = obj->obj_members;
  465.     n = clgetsize(&obj->obj_class);
  466.     while (--n >= 0)
  467.     mark(p++);
  468. }
  469.  
  470. /* markvector - mark a vector */
  471. static void markvector(vect)
  472.   VECTOR *vect;
  473. {
  474.     VALUE *p;
  475.     int n;
  476.     p = vect->vec_data;
  477.     n = vect->vec_size;
  478.     while (--n >= 0)
  479.     mark(p++);
  480. }
  481.  
  482. /* compact - compact vector space */
  483. static void compact()
  484. {
  485.     VSEGMENT *vseg;
  486.  
  487.     /* store the current segment information */
  488.     if (vscurrent)
  489.     vscurrent->vs_free = vfree;
  490.  
  491.     /* compact each vector segment */
  492.     for (vseg = vsegments; vseg != NULL; vseg = vseg->vs_next)
  493.     compact_vector(vseg);
  494.  
  495.     /* make the first vector segment current */
  496.     if ((vscurrent = vsegments) != NULL) {
  497.     vfree = vscurrent->vs_free;
  498.     vtop = vscurrent->vs_top;
  499.     }
  500. }
  501.  
  502. /* getblocksize - get the size of a block */
  503. static int getblocksize(hdr)
  504.   HDR *hdr;
  505. {
  506.     switch (hdr->hdr_type) {
  507.     case DT_CLASS:
  508.     return (ALLOCSIZE(sizeof(CLASS)));
  509.     case DT_OBJECT:
  510.     return (ALLOCSIZE(sizeof(OBJECT)
  511.          +  (clgetsize(&((OBJECT *)hdr)->obj_class) - 1) * sizeof(VALUE)));
  512.     case DT_VECTOR:
  513.     return (ALLOCSIZE(sizeof(VECTOR)
  514.          +  (((VECTOR *)hdr)->vec_size - 1) * sizeof(VALUE)));
  515.     case DT_STRING:
  516.     return (ALLOCSIZE(sizeof(STRING)
  517.          +  ((STRING *)hdr)->str_size - 1));
  518.     case DT_DICTIONARY:
  519.     return (ALLOCSIZE(sizeof(DICTIONARY)));
  520.     case DT_VAR:
  521.     return (ALLOCSIZE(sizeof(DICT_ENTRY)));
  522.     }
  523.     error("Bad block type: %d",hdr->hdr_type);
  524.     return (0);
  525. }
  526.  
  527. /* compact_vector - compact a vector segment */
  528. static void compact_vector(vseg)
  529.   VSEGMENT *vseg;
  530. {
  531.     AUNIT *vdata,*vnext,*vfree;
  532.     VALUE *vp,*nextvp;
  533.     int vsize;
  534.     HDR *hdr;
  535.  
  536.     vdata = vnext = vseg->vs_data;
  537.     vfree = vseg->vs_free;
  538.     while (vdata < vfree) {
  539.     hdr = (HDR *)vdata;
  540.     vsize = getblocksize(hdr);
  541.     if (hdr->hdr_flags & MARK) {
  542.         hdr->hdr_flags &= ~MARK;
  543.         for (vp = hdr->hdr_chain; vp != NULL; vp = nextvp) {
  544.         nextvp = vp->v.v_chain;
  545. /*printf("FIXUP: H:%04x T:%02d V:%04x C:%04x N:%04x\n",
  546.        hdr,hdr->hdr_type,vp,nextvp,vnext);*/
  547.         vp->v.v_hdr = (HDR *)vnext;
  548.         }
  549.         hdr->hdr_chain = NULL;
  550.         if (vdata == vnext) {
  551. /*printf("KEEPING: %04x T:%02d\n",hdr,hdr->hdr_type);*/
  552.         vdata += vsize;
  553.         vnext += vsize;
  554.         }
  555.         else {
  556. /*printf("MOVING: %04x->%04x T:%02d\n",hdr,vnext,hdr->hdr_type);*/
  557.         while (--vsize >= 0)
  558.             *vnext++ = *vdata++;
  559.         }
  560.     }
  561.     else {
  562. /*printf("FREEING: %04x T:%02d\n",hdr,hdr->hdr_type);*/
  563.         vdata += vsize;
  564.     }
  565.     }
  566.     vseg->vs_free = vnext;
  567. }
  568.